#include <iostream>

using namespace std;
using LL=long long;


int p;
int qmi(int a,int b)
{
	int ret=1;
	while(b)
	{
		if(b&1)
		{
			ret=(LL)ret*a%p;
		}
		a=(LL)a*a%p;
		b>>=1;
	}
	return ret;
}
int c(int a,int b)
{
	int ret=1;
	for(int i=1,j=a;i<=b;i++,j--)
	{
		ret=(LL)ret*j%p;
		ret=(LL)ret*qmi(i,p-2)%p;
	}
	return ret;
}
int locas(LL a,LL b)
{
	if(a<p && b<p)
		return c(a,b);
	else
		return (LL)c(a%p,b%p)*locas(a/p,b/p)%p;	
}
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		LL a,b;
		cin>>a>>b>>p;
		cout<<locas(a,b)<<endl;
	}
	return 0;
}
